#include "linearList.h"
using namespace std;
//结点构造
listNode::listNode(float nodeData, listNode* succ){
    data = nodeData;
    next = succ;
}
//结点析构
listNode::~listNode(){}
//链表构造
linkList::linkList(const int& size, float arr[]) : firstNode(nullptr), lastNode(nullptr), listSize(0) {
    for (int i = 0; i < size; ++i) {
        tailInsertItem(arr[i]);
    }
}
//链表析构
linkList::~linkList() {
    listNode* current = firstNode;
    while (current != nullptr) {
        listNode* temp = current;
        current = current->next;
        delete temp;
    }
}
//链表头插
bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new (std::nothrow) listNode(item, firstNode->next);
    if (!newNode) {
        return false;
    }
    firstNode->next = newNode;
    if (listSize == 0) {
        lastNode = newNode;
    }
    ++listSize;
    return true;
}
//链表尾插
bool linkList::tailInsertItem(const float& item) {
    listNode* newNode = new (std::nothrow) listNode(item, nullptr);
    listNode* newNode1 = new (std::nothrow) listNode(item, nullptr);
    if (!newNode) {
        return false;
    }
    if (listSize == 0) {
        firstNode = newNode1;
        firstNode->next = newNode;
        lastNode = newNode;
    } else {
        lastNode->next = newNode;
        lastNode = newNode;
    }
    ++listSize;
    return true;
}
//链表插入特定位置
int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) {
        return -1;
    }

    if (index == 0) {
        if (headInsertItem(item)) {
            return 0;
        } else {
            return -1;
        }
    } else if (index == listSize) {
        if (tailInsertItem(item)) {
            return listSize - 1;
        } else {
            return -1;
        }
    } else {
        listNode* prev = firstNode->next;
        for (int i = 0; i < index - 1; ++i) {
            prev = prev->next;
        }
        listNode* newNode = new (std::nothrow) listNode(item, prev->next);
        if (!newNode) {
            return -1;
        }
        prev->next = newNode;
        ++listSize;
        return index;
    }
}
//链表按值删除
int linkList::deleteItem(const float& item) {
    if (listSize == 0) {
        return -1;
    }

    int deleteCount = 0;
    listNode* current = firstNode->next;
    listNode* prev = nullptr;

    while (current != nullptr) {
        if (current->data == item) {
            listNode* temp = current;
            if (prev == nullptr) { // 删除第一个节点
                firstNode->next = current->next;
                if (firstNode->next == nullptr) { // 链表为空
                    lastNode = nullptr;
                }
            } else {
                prev->next = current->next;
                if (current->next == nullptr) { // 删除最后一个节点
                    lastNode = prev;
                }
            }
            current = current->next;
            delete temp;
            --listSize;

            return deleteCount;
        } else {
            prev = current;
            current = current->next;
        }
        ++deleteCount;
    }

    if (deleteCount == 0) {
        return -1;
    }
    return deleteCount;
}
//按位置查找元素
bool linkList::locate(const int& index, float& val) {
    if (index < 0 || index >= listSize) {
        return false;
    }

    listNode* current = firstNode->next;
    for (int i = 0; i < index; ++i) {
        current = current->next;
    }
    val = current->data;
    return true;
}

// 按值查找元素
int linkList::locate(const float& item) {
    listNode* current = firstNode->next;
    int index = 0;
    while (current != nullptr) {
        if (current->data == item) {
            return index;
        }
        current = current->next;
        ++index;
    }
    return -1;
}

// 升序排序链表（选择排序）
void linkList::ascendingOrder(){
    if (listSize < 2) {
        return; // 已经有序
    }

    listNode* disorderNode = firstNode->next;

    while (disorderNode != lastNode){
        listNode* minNode = disorderNode;
        listNode* curNode = disorderNode->next;

        // 找到剩余链表中的最小节点
        while (curNode != nullptr){
            if (curNode->data < minNode->data){
                minNode = curNode;
            }
            curNode = curNode->next;
        }

        // 如果找到的最小节点不是当前的 disorderNode，则交换数据
        if (minNode != disorderNode){
            float temp = disorderNode->data;
            disorderNode->data = minNode->data;
            minNode->data = temp;
        }

        // 移动到下一个节点
        disorderNode = disorderNode->next;
    }
}
//链表翻转
void linkList::reverse() {
    if (listSize < 2) {
        return; // 无需反转
    }

    listNode* prev = nullptr;
    listNode* current = firstNode->next;
    lastNode = firstNode->next; // 反转后原来的第一个节点变为最后一个

    while (current != nullptr) {
        listNode* nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }

    firstNode->next = prev;
}
//顺序表构造
sequenceList::sequenceList(const int& a, const int& b, float c[])
{
    maxCapcity = a;
    curNumberOfItem = b;
    myList = new float[a];
    for(int i = 0; i < curNumberOfItem; i++)
    {
        myList[i] = c[i];
    }
}
//顺序表析构
sequenceList::~sequenceList()
{
    delete []myList;
}
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }


        curNode = curNode->next;
    }
}

//顺序表尾插
bool sequenceList::addItem(const float& f)
{
    if(curNumberOfItem < maxCapcity){
        myList[curNumberOfItem++] = f ;
        return true;}
        return false;
}
//顺序表插入
bool sequenceList::insertItem(const int& i,const float& j)
{
    if(i < 0 || i > curNumberOfItem)return false;
    for(int k = curNumberOfItem;k >= i;k--){
        myList[k]=myList[k-1];
    }
    myList[i] = j;
    curNumberOfItem++;
    return true;
}
//顺序表删除
int sequenceList::deleteItem(const float& i)
{
    for(int k=0;k<curNumberOfItem;k++){
        if(myList[k]==i){
            for(int j=k;j<curNumberOfItem-1;j++)
                myList[j]=myList[j+1];
            curNumberOfItem--;
            return k;
    }
}
    return -1;
}
//顺序表按位置查找
bool sequenceList::locate(const int& p, float& val)
{
    if(p < 0 || p > curNumberOfItem)return false;
    val = myList[p-1];
    return true;
}
//顺序表按值查找
int sequenceList::locate(const float& i)
{
    for(int k=0;k<curNumberOfItem;k++){
        if(myList[k]==i){
            return k;
    }
}
    return -1;
}
//顺序表翻转
void sequenceList::reverse()
{
    const int o = curNumberOfItem;
    float relist[o];
    for(int i = 0;i < o;i++)
        relist[i] = myList[i];
    for(int i = 0;i < o;i++)
        myList[i] = relist[curNumberOfItem - i - 1];
}
//链表取头结点
listNode* linkList::GetfirstNode()
{
    return firstNode;
}
//链表取尾结点
listNode* linkList::GetlastNode()
{
    return lastNode;
}
//链表取长度值
int linkList::GetlistSize()
{
    return listSize;
}
//链表设置长度值
void linkList::SetlistSize(int a)
{
    listSize = a;
}
//链表设置尾结点
void linkList::SetlastNode(listNode *a)
{
    lastNode->next = a->next;
    while(lastNode->next)
        lastNode = lastNode->next;
}
//链表合并
void linkList::add(linkList& b){
    this->listSize += b.listSize;
    this->lastNode->next = b.firstNode->next;
    this->lastNode = b.lastNode;
}
//链表合并并倒序
    void merge(linkList& list1, linkList& list2)
{
    list1.add(list2);
    list1.ascendingOrder();
    list1.reverse();
}

